The present invention relates generally to the field of computer memory management, and more particularly to page replacement algorithms for use with solid-state drives.
Virtual memory is a memory management technique that utilizes hardware and software to map virtual addresses to physical addresses in memory (e.g., random access memory [RAM]). In general, virtual memory appears as a contiguous range of virtual addresses to computer processes. In reality, the virtual addresses can be associated with discontiguous physical addresses. In addition, the physical addresses can be distributed between memory and secondary storage (e.g., a hard disk drive [HDD] or a solid-state drive [SSD]). Distributing physical addresses between memory and secondary storage enables the number of virtual addresses to exceed the number of physical addresses that are available in memory.
Paging is one technique for managing data that is distributed between memory and secondary storage. Computing systems that use the paging technique store data in pages. A page is a fixed-length contiguous block of virtual memory. A page is also the smallest unit of data that is addressed in memory in such systems. A page table associates each page with a virtual address and a physical address. In other words, the page table is a data structure that maps the virtual address of each page to a physical address. The mappings are known as page table entries (PTEs). When a computer process references (i.e., reads/requests access to) or modifies (i.e., overwrites) data in memory, the page table enables the computing system to translate the virtual address into the physical address where the data is stored. In general, a memory management unit (MMU) receives references to virtual addresses and translates the virtual addresses into physical addresses. In some cases, each PTE includes a bit that indicates whether the respective page is stored in memory or secondary storage. If a page is referenced and the bit indicates that the page is stored in secondary storage, a page fault occurs. When this type of page fault occurs, the computing system loads the referenced page into memory from secondary storage. Another type of page fault occurs when an operating system and/or memory management unit must make room in memory to store recently referenced or modified pages. When this type of situation occurs an existing page in physical memory is paged out and written to secondary storage so that memory can store the recently referenced or modified page.